package com.linzm.leetcode.mid.tree.其他;

import java.util.*;

/**
 * @Author zimingl
 * @Date 2023/3/19 15:10
 * @Description: 二叉搜索树中的众数
 *
 * 树中节点的数目在范围 [1, 104] 内
 * -105 <= Node.val <= 105
 */
public class Demo25FindMode501 {
    public int[] findMode(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        List<Integer> list = new ArrayList<>();
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node != null) {
                if (node.left != null) stack.push(node.left);
                stack.push(node);
                stack.push(null);
                if (node.right != null) stack.push(node.right);
            } else {
                TreeNode addNode = stack.pop();
                list.add(addNode.val);
            }
        }
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> res = new ArrayList<>();
        for (Integer val : list) {
            map.put(val, map.getOrDefault(val, 0) + 1);
        }
        Integer max = map.values().stream().max(Comparator.naturalOrder()).get();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue().equals(max)) {
                res.add(entry.getKey());
            }
        }
        return res.stream().mapToInt(num -> num).toArray();
    }
}
